Kleene star

#formal_language_theory

Definition

For alphabet $L$ , the Kleene star yields a language, defined as the set of all words over alphabet $L$ , i.e.

L^* = \bigcup_{n \in \mathbb{N}} L^n

where $L^0 = \{\epsilon\}$ ( $\epsilon$ empty word) and $L^{n+1} = L \cdot L^n$ (concatenation)

Notes

the Kleene star $A^*$ of an alphabet is a free monoid on the set $A$
(see monoid and free monoid)

References

M. Avanzini, Lecture Notes, Topic: “finite automata.” M1-AL, Centre Inria d’Université Côte d’Azur, 2021. https://www-sop.inria.fr/members/Martin.Avanzini/teaching/2021/AL/slides/w1.pdf
https://en.wikipedia.org/wiki/Kleene_star
https://en.wikipedia.org/wiki/Free_monoid#Kleene_star